import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;


//Hikaru
public class ArrayManipluation {
	
 /**
	Using two HashMaps, one records the length of consecutive sequences 
	before element(inclusive) and one records the length of consecutive 
	sequences after element(inclusive). If the ith element extends an 
	existing sequence, then updating both boundaries. 
	Single for loop and done:
	*/
	public int longestConsecutive(int[] num) {
	    HashMap<Integer, Integer> prevCons = new HashMap<Integer, Integer>();
	    HashMap<Integer, Integer> postCons = new HashMap<Integer, Integer>();
	    int longest = 1;

	    for(Integer number: num){
	        if(prevCons.containsKey(number))
	            continue;
	        if(prevCons.containsKey(number - 1))
	            prevCons.put(number, 1 + prevCons.get(number - 1));
	        else
	            prevCons.put(number, 1);

	        if(postCons.containsKey(number + 1))
	            postCons.put(number, 1 + postCons.get(number + 1));
	        else
	            postCons.put(number, 1);

	        //update left boundary
	        if(prevCons.containsKey(number - 1)){
	        	//record the number of consecutive value before the current value
	            int newPost = prevCons.get(number - 1) + postCons.get(number);
	            //put the newPost to the most left consecutive value.
	            postCons.put(number - prevCons.get(number - 1), newPost);
	            longest = Math.max(longest, newPost);
	        }
	        //update right boundary
	        if(postCons.containsKey(number + 1)){
	        	//record the number of consecutive value after the current value
	            int newPrev = postCons.get(number + 1) + prevCons.get(number);
	          //put the newPrev to the most right consecutive value.
	            prevCons.put(number + postCons.get(number + 1), newPrev);
	            longest = Math.max(longest, newPrev);
	        }
	    }
	    return longest;
	}
	
	//3 sum
	public HashSet<TreeSet<Integer>> ThreeSum(int[] arr, int sum){
		if(arr.length == 0  || arr == null){
			return null;
		}
		int subSolution = 0;
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		TreeSet<Integer> set = new TreeSet<Integer>();
		HashSet<TreeSet<Integer>> result = new HashSet<TreeSet<Integer>>();
		for(int k = 0; k < arr.length; k++){
			hash.put(arr[k], k);
		}
		
		for(int i = 0; i < arr.length; i++){
			subSolution = sum - arr[i];
			for(int j = 0; j < arr.length ; j++){
				if(hash.containsKey(subSolution - arr[j])
					&&i!=j 
					&& arr[j] != arr[i]
					&& arr[j] != arr[hash.get(subSolution - arr[j])] 
					&& arr[i] != arr[hash.get(subSolution - arr[j])]){	
					set.add(arr[hash.get(subSolution - arr[j])]);
					set.add(arr[j]);
					set.add(arr[i]);
					
					TreeSet<Integer> tempSet = (TreeSet<Integer>) set.clone();
					result.add(tempSet);
					set.clear();
				
				}
				
			}
		}
		return result;
	}
	
	public int[] largestSubarraySum(int[] arr){
		if(arr.length == 0 || arr == null){
			return null;
		}
		int result = Integer.MIN_VALUE;
		int sum = 0;
		int lastIndex = 0;
		int firstIndex = 0;
		for(int i = 0; i < arr.length; i++){
			sum += arr[i];
			if(sum > result || arr[i] == 0){
				result = sum;
				lastIndex = i;
			}
		}
		
		sum = 0;
		for(int j = lastIndex; j >=0; j--){
			sum += arr[j];
			if(sum > result || arr[j] == 0){
				result = sum;
				firstIndex = j;
			}
		}
		
		int[] resultArray = new int[lastIndex - firstIndex + 1];
		resultArray = Arrays.copyOfRange(arr, firstIndex, lastIndex+1);
		for(int k : resultArray){
			System.out.print(k + " ");
		}
		return resultArray;
	}
	//rotate a matrix 90 degree
	public int[][] rotate(int[][] arr){
		if(arr == null)
			return null;
		
		int preRow = arr.length;
		int preCol = arr[0].length;
		int[][] result = new int[preCol][preRow];
		
		for(int i = 0; i < result.length; i++){
			int temp = preRow - 1;
			for(int j = 0; j < result[i].length; j++){
				result[i][j] = arr[temp--][i];
				System.out.print(result[i][j]+ " ");
			}
			System.out.println();
		}
		
		
		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayManipluation am = new ArrayManipluation();
		int[] arr = {100, 101,102, 4, 201, 200, 1, 3, 2, 5};
		int[] test = {-1, 0, 1, 5, -2, -3};
		int[] test2 = {-2, 3, 4, 6, -10, 20, -5, 6};
		int[][] test3 ={{1,2,3,4}, {5,6,7,8},{9,10,11,12}};
		System.out.println(am.ThreeSum(test, 0).toString());
		System.out.println(am.longestConsecutive(arr));
		am.largestSubarraySum(test2);
		System.out.println();
		am.rotate(test3);
	}

}
